package com.jack.leetcode.eachproblem_2020;

/**
 * Created by zhang_j on 2020/11/25
 */
public class 上升下降字符串 {

    public String sortString(String s) {

        int[] dp = new int[26];
        int index = -1, max = 0;
        for(char c : s.toCharArray()){
            dp[c - 'a']++;
            if(dp[c - 'a'] > max){
                index = c - 'a';
                max = dp[c - 'a'];
            }
        }
        StringBuilder result = new StringBuilder();
        boolean reverse = false;
        while(dp[index] != 0){
            if(reverse){
                for(int i = 25;i >= 0;i--){
                    if(dp[i] != 0){
                        result.append((char)(i + 'a'));
                        dp[i]--;
                    }
                }
                reverse = false;
            }else{
                for(int i = 0;i < 26;i++){
                    if(dp[i] != 0){
                        result.append((char)(i + 'a'));
                        dp[i]--;
                    }
                }
                reverse = true;
            }
        }
        return result.toString();
    }
}
